package ee.homework.seventh;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

import ee.homework.seventh.Node.Color;

public class DirectGraphTraversal {

	private String[] files = new String[] { "G1.txt", "G2.txt", "G3.txt" };
	private Map<Node, List<Node>> adjList;

	public static void main(String[] args) {
		new DirectGraphTraversal().run();
	}

	private void run() {
		for (int i = 0; i < files.length; i++) {
			adjList = readFile(new File("data\\" + files[i]));
			List<Node> bfs = breadthFirstSearch(adjList, findNode(adjList, 1));
			System.out.println("Node count: " + bfs.size() + ", nodes: " + bfs);
			List<Node> dfs = depthFirstSearch(adjList, findNode(adjList, 1));
			System.out.println("Node count: " + dfs.size() + ", nodes: " + dfs);
		}
	}

	private Map<Node, List<Node>> readFile(File graph) {
		Map<Node, List<Node>> adjList = new HashMap<Node, List<Node>>();
		try {
			BufferedReader reader = new BufferedReader(new FileReader(graph));
			String line = null;
			List<Node> vertices = new LinkedList<Node>();
			while ((line = reader.readLine()) != null) {
				String[] splitLine = line.split(">");

				int sourceKey = Integer.parseInt(splitLine[0].trim());
				Node source = findNode(vertices, sourceKey);
				if (source == null) {
					source = new Node(sourceKey);
					vertices.add(source);
				}

				int destinationKey = Integer.parseInt(splitLine[1].trim());
				Node destination = findNode(vertices, destinationKey);
				if (destination == null) {
					destination = new Node(destinationKey);
					vertices.add(destination);
				}

				Node node = findNode(adjList, sourceKey);
				if (node != null) {
					List<Node> adjVertices = adjList.get(node);
					adjVertices.add(destination);
					adjVertices = sort(adjVertices);
					adjList.put(node, adjVertices);
				} else {
					List<Node> adjVertices = new LinkedList<Node>();
					adjVertices.add(destination);
					adjList.put(source, adjVertices);
				}
			}
		} catch (FileNotFoundException e) {
			System.out.println("File " + graph.getName() + " not found!");
			System.exit(1);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return adjList;
	}

	private Node findNode(Map<Node, List<Node>> adjList, int key) {
		Node node = null;
		for (Map.Entry<Node, List<Node>> vertex : adjList.entrySet()) {
			if (vertex.getKey().getKey() == key) {
				node = vertex.getKey();
				break;
			}
		}
		return node;
	}

	private Node findNode(List<Node> adjVertices, int key) {
		Node node = null;
		for (Node vertex : adjVertices) {
			if (vertex.getKey() == key) {
				node = vertex;
				break;
			}
		}
		return node;
	}

	private List<Node> breadthFirstSearch(Map<Node, List<Node>> adjList,
			Node start) {
		clearNodes(adjList);
		start.setColor(Color.GRAY);
		start.setDistance(0);
		Queue<Node> queue = new LinkedBlockingQueue<Node>();
		queue.offer(start);
		List<Node> visited = new LinkedList<Node>();
		while (!queue.isEmpty()) {
			Node next = queue.poll();
			List<Node> adjVers = adjList.get(next);
			if (adjVers != null) {
				for (Node adjNode : adjVers) {
					if (adjNode.getColor() == Color.WHITE) {
						adjNode.setColor(Color.GRAY);
						adjNode.setDistance(next.getDistance() + 1);
						adjNode.setPredecessor(next);
						queue.offer(adjNode);
					}
				}
			}
			next.setColor(Color.BLACK);
			visited.add(next);
		}
		return visited;
	}

	private List<Node> depthFirstSearch(Map<Node, List<Node>> adjList,
			Node start) {
		clearNodes(adjList);
		start.setColor(Color.GRAY);
		start.setDistance(0);
		Queue<Node> queue = new LinkedBlockingQueue<Node>();
		queue.offer(start);
		List<Node> visited = dfsVisit(adjList, start);
		return visited;
	}

	private List<Node> dfsVisit(Map<Node, List<Node>> adjList, Node node) {
		node.setColor(Color.GRAY);
		List<Node> list = new LinkedList<Node>();
		List<Node> adjVers = adjList.get(node);
		list.add(node);
		if (adjVers != null) {
			for (Node adjNode : adjVers) {
				if (adjNode.getColor() == Color.WHITE) {
					adjNode.setPredecessor(node);
					list.addAll(dfsVisit(adjList, adjNode));
				}
			}
		}
		node.setColor(Color.BLACK);
		return list;
	}

	private List<Node> sort(List<Node> adjVertices) {
		for (int i = 0; i < adjVertices.size(); i++) {
			Node first = adjVertices.get(i);
			for (int j = i + 1; j < adjVertices.size(); j++) {
				Node second = adjVertices.get(j);
				if (second.getKey() < first.getKey()) {
					adjVertices.set(i, second);
					adjVertices.set(j, first);
				}
			}
		}
		return adjVertices;
	}

	private void clearNodes(Map<Node, List<Node>> adjList) {
		for (Map.Entry<Node, List<Node>> item : adjList.entrySet()) {
			if (item.getKey().getColor() != Color.WHITE) {
				item.getKey().setColor(Color.WHITE);
				item.getKey().setDistance(Integer.MAX_VALUE);
				item.getKey().setPredecessor(null);
			}
			for (Node node : item.getValue()) {
				if (node.getColor() != Color.WHITE) {
					node.setColor(Color.WHITE);
					node.setDistance(Integer.MAX_VALUE);
					node.setPredecessor(null);
				}
			}
		}
	}
}
